#pragma once
#include <sys/cdefs.h>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <new>
#include "memory_cpp.hpp"
namespace esmd{
template <typename T>
struct list{
  __always_inline list(memrec_t *rec, size_t initial_size=32) {
    v = allocate<T>(initial_size, rec);
    max_cnt = initial_size;
    cur_cnt = 0;
  }
  __always_inline list(const char *name, size_t initial_size=32) : list(get_memrec(name), initial_size) {}
  __always_inline list(size_t initial_size, memrec_t *rec) : list(rec, initial_size) {}
  __always_inline list(size_t initial_size, const char *name) : list(name, initial_size) {}
  __always_inline list(const list &from) : v(from.v), max_cnt(from.max_cnt), cur_cnt(from.cur_cnt), exported(true) {
    puts("WARNING: copy constructor is called for list!");
  }
  void grow(size_t n) {
    if (n > 0){
      v = reallocate(v, max_cnt + n);
      max_cnt += n;
    }
  }
  __always_inline void grow(){ grow((max_cnt + 1) >> 1); }
  __always_inline void grow_to(size_t n) { grow(n - max_cnt); }
  __always_inline T *get_slot() {
    if (cur_cnt == max_cnt) grow();
    return v + cur_cnt ++;
  }
  __always_inline void append(const T &val) {
    const T tmp = val;
    if (cur_cnt == max_cnt) grow();
    v[cur_cnt] = tmp;
    cur_cnt ++;
  }
  __always_inline T* extract(){
    exported = true;
    return v;
  }
  __always_inline T &operator[](size_t i){
    return v[i];
  }
  __always_inline const T &operator[](size_t i) const {
    return v[i];
  }
  __always_inline void sort() {
    std::sort(v, v + cur_cnt);
  }
  template<typename Compar>
  __always_inline void sort(const Compar &comp) {
    std::sort(v, v + cur_cnt, comp);
  }
  template<typename Compar>
  __always_inline size_t bisect_begin(const T &val, Compar &comp){
    size_t begin = 0, end = cur_cnt;
    while (begin != end) {
      size_t mid = (begin + end) >> 1;
      if (comp(v[mid], val)) {/*comp(a, b): a<b*/
        begin = mid + 1;
      } else {
        end = mid;
      }
    }
    return begin;
  }
  template<typename Compar>
  __always_inline size_t bisect_end(const T &val, Compar &comp){
    size_t begin = 0, end = cur_cnt;
    while (begin != end) {
      size_t mid = (begin + end) >> 1;
      if (comp(val, v[mid])) {/*comp(a, b): a<b*/
        end = mid;
      } else {
        begin = mid + 1;
      }
    }
    return begin;
  }
  template<typename U>
  __always_inline size_t bisect_begin(const U &val) {
    std::less<T> lt;
    return bisect_begin(val, lt);
  }
  template<typename U>
  __always_inline size_t bisect_end(const U &val) {
    std::less<T> lt;
    return bisect_end(val, lt);
  }
  __attribute__((noinline)) ~list() {
    if (!exported) {
      deallocate(v);
    }
  }
  template<typename ...Ts>
  __always_inline T &new_slot(Ts... args){
    if (cur_cnt >= max_cnt) grow();
    new (&v[cur_cnt++])T(args...);
    return v[cur_cnt - 1];
  }
  __always_inline size_t size(){
    return cur_cnt;
  }
  __always_inline size_t set_size(size_t size_new){
    if (size_new > max_cnt) grow_to(size_new);
    cur_cnt = size_new;
  }
  __always_inline void clear(){
    cur_cnt = 0;
  }
  __always_inline T *begin(){
    return v;
  }
  __always_inline T *end(){
    return v + cur_cnt;
  }
private:
  T *v;
  size_t max_cnt, cur_cnt;
  bool exported = false;
};

// template <typename T>
// struct linked_list{
//   struct node {
//     node *next;
//     T data;
//   };
//   struct iterator {
//     node *cur;
//     bool operator == (const iterator &o){
//       return cur == o.cur;
//     }
//     bool operator != (const iterator &o){
//       return cur != o.cur;
//     }
//     T &operator *(){
//       return cur->data;
//     }
//     iterator &operator++(){
      
//     }
//   };
// private:
//   node *head;
  
//   __always_inline iterator start(){
//     return iterator{head};
//   }
//   __always_inline iterator end(){
//     return iterator{nullptr};
//   }
//   __always_inline node end(){
//   }
// }
//  ;
}

